package combinationsumiii216

func CombinationSum3(k int, n int) [][]int {
	result := [][]int{}
	combination := []int{}
	backtrack(k, n, 1, combination, &result)
	return result
}

// backtrack is a helper function that performs the backtracking algorithm.
// It tries to build combinations of numbers that sum up to the target value n.
// It takes the current combination, the starting number, and the result slice as arguments.
// @param k: The number of elements in the combination.
// @param n: The target sum.
// @param start: The starting number for the current combination. The init start is 1, because we need to use 1-9.
// @param combination: The current combination being built.
// @param result: The slice to store the valid combinations.
// @return: None
func backtrack(k int, n int, start int, combination []int, result *[][]int) {
	if len(combination) == k && n == 0 {
		// If the combination has k elements and the sum is 0, add it to the result.
		combinationCopy := make([]int, k)
		copy(combinationCopy, combination)
		*result = append(*result, combinationCopy) // if code reach here, it means we find a valid result item.
		return
	}

	for i := start; i <= 9; i++ {
		if n < i {
			// If the remaining sum is less than the current number, break the loop.
			break
		}
		combination = append(combination, i)        // Add the current number to the combination.
		backtrack(k, n-i, i+1, combination, result) // Recur with the next number.
		// no matter if we find a result item by backtrack, we will remove the last number from the combination so that we can scan the remain number in this loop.
		combination = combination[:len(combination)-1] // Backtrack by removing the last number.
	}

	// if the code reach here, it means current combination is not valid, so we need to backtrack
}
